package momo.multitree.util;

import momo.multitree.algo.AllTreeVisitor;
import momo.multitree.structure.*;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.Vector;


public class JackAlgo
{
	private Vector<Edge> swapEdges[];
	private Vector<Edge> edgesOfInitTree;
	private Vector<Edge> outEdgesOfInitTree;
	private Graph initTree;
	
	private LinkedHashSet<AllTreeVisitor> visitors;
	
	private int mainCounter = 0;
	
	public JackAlgo()
	{
		edgesOfInitTree = new Vector<Edge>();
		outEdgesOfInitTree = new Vector<Edge>();
		initTree = new Graph();
		
		visitors = new LinkedHashSet<AllTreeVisitor>();
	}
	
	public void addVisitor(AllTreeVisitor visitor)
	{
		this.visitors.add(visitor);
	}
	
	public void visit(Graph g)
	{
		for(Node root: g.getNodes())
		{
			mainCounter ++;
			Tree t = new Tree(root, g);
			for(AllTreeVisitor visitor: visitors)
				visitor.visit(t);
		}
	}
	
	public void generateSpanningGraph(Graph g)
	{
		setup(g);
//		System.out.println("Start of algo");
		visit(initTree);
		findChildren(edgesOfInitTree, edgesOfInitTree.size()-1);
//		System.out.println("Count: " + mainCounter);
	}
	
	private void findChildren(Vector<Edge> allEdges, int counter)
	{
//		System.out.println("Counter: " + counter);
		if ( counter < 0 )
			return;
		
//		for(Edge e: allEdges)
//			System.out.println("Id: " + e.toString());
		
		for(int i=0; i<swapEdges[counter].size(); i++)
		{
			Vector<Edge> curAllEdges = new Vector<Edge>(allEdges);
//			Edge toRemove = curAllEdges.remove(counter);
			curAllEdges.remove(counter);
			Edge toAdd = swapEdges[counter].elementAt(i);
			Graph g = isWantedGraph(curAllEdges, toAdd);
			if ( g != null )
			{
				// wanted graph
				visit(g);
//				System.out.println(g.toString());
				
				curAllEdges.add(toAdd);
//				System.out.println("*** Child");
				findChildren(new Vector<Edge>(g.getEdges()), counter-1);
			}
		}
		Vector<Edge> curAllEdges = new Vector<Edge>(allEdges);
//		System.out.println("*** Bro");
		findChildren(curAllEdges, counter-1);
	}
	
	public void setup(Graph g)
	{
		initDFS(g);
		initSwapEdge(g);
	}
	
	public Graph isWantedGraph(Vector<Edge> allEdges, Edge toAdd)
	{
		if ( allEdges.contains(toAdd) )
			return null;
		
		Graph g = new Graph();
		for(Edge e: allEdges)
			g.add(e);
		g.add(toAdd);
		if ( isConnectedAndNoCycles(g) )
			return g;
		return null;
	}
	
	public Graph isWantedGraph(Vector<Edge> allEdges, Edge toRemove, Edge toAdd)
	{
		Graph g = new Graph();
		for(int i=0; i<allEdges.size(); i++)
		{
			Edge e = allEdges.get(i);
			if ( e != toRemove )
				g.add(e);
		}
		g.add(toAdd);
		if ( isConnectedAndNoCycles(g) )
			return g;
		return null;
	}
	
	public boolean isConnectedAndNoCycles(Graph g)
	{
		
		LinkedHashSet<Node> visitedNode = new LinkedHashSet<Node>();
		LinkedHashSet<Edge> visitedEdge = new LinkedHashSet<Edge>();
		
		Set<Node> tmpSet = g.getNodes();
		if ( !tmpSet.isEmpty() )
		{
			Node[] nodes = tmpSet.toArray(new Node[0]);
			Node root = nodes[0];
			
			Vector<Node> toVisit = new Vector<Node>();
			
			toVisit.add(root);
			
			while ( toVisit.size() > 0 )
			{
				Node currNode = toVisit.remove(0);
				visitedNode.add(currNode);
				
				Set<Edge> set = g.getEdgesOfNode(currNode);
				Iterator<Edge> iter = set.iterator();
				
				while ( iter.hasNext() )
				{
					Edge edge = iter.next();
					Node toNode = edge.nextNode(currNode);
					
					if ( visitedNode.contains(toNode) )
					{
						if ( !visitedEdge.contains(edge) )
							return false;
					}else {
						visitedNode.add(toNode);
						toVisit.add(toNode);
						visitedEdge.add(edge);
					}
				}
			}
			return tmpSet.size() == visitedNode.size();
		}
		return false;
	}
	
	private void initSwapEdge(Graph g)
	{
		int noOfEdges = g.getNoOfNodes() - 1;
		swapEdges = new Vector[noOfEdges];
		for(int i=0; i<swapEdges.length; i++)
			swapEdges[i] = new Vector<Edge>();
		
		for(int i=0; i<edgesOfInitTree.size(); i++)
		{
			Edge toRemove = edgesOfInitTree.elementAt(i);
			for(int j=0; j<outEdgesOfInitTree.size(); j++)
			{
				Edge toAdd = outEdgesOfInitTree.elementAt(j);
				Graph graph = isWantedGraph(edgesOfInitTree, toRemove, toAdd);
				if ( graph != null )
					swapEdges[i].add(toAdd);
			}
		}
	}
	
	private void initDFS(Graph graph)
	{
		HashSet<Node> visited = new HashSet<Node>();
		HashSet<Edge> edgeVisited = new HashSet<Edge>();
		
		Node[] nodes = graph.getNodes().toArray(new Node[0]);
		Node root = nodes[0];
		
		visited.add(root);
		
		initDFS(graph, visited, null, root);
	}
	
	private void initDFS(Graph graph, HashSet<Node> visited, Node parent, Node currNode)
	{
		visited.add(currNode);
		
		Set<Edge> set = graph.getEdgesOfNode(currNode);
		Iterator<Edge> iter = set.iterator();
		while ( iter.hasNext() )
		{
			Edge edge = iter.next();
			Node toNode = edge.nextNode(currNode);
			
			if ( !visited.contains(toNode) )
			{
				//add to T_0 tree;
				edgesOfInitTree.add(edge);
				initTree.add(edge);
				initDFS(graph, visited, currNode, toNode);
			}else if ( toNode != parent )
			{
				if ( !outEdgesOfInitTree.contains(edge) )				
					outEdgesOfInitTree.add(edge);
			}
		}
	}
	
}//end of JackAlgo
